/********************************************************************************/
/*         @Author:         Mogutin Kiril                                       */
/*          Creation Date:  27/07/2010                                          */
/*          Last Modified:  30/07/2010                                          */
/*         @Brief:          ADT Binary Tree:                                    */
/*                          The tree is a structure for quick search of data.   */
/*                          This tree is a multi set which means the key by     */
/*                          which data is sorted is the data. The tree can      */
/*                          contain the same data num of times.                 */
/*                          Access to the data in the tree enabled by iterators.*/
/*                          The sort of data in the tree is done by compare     */
/*                          function (Less type) which user must provide.       */
/********************************************************************************/

#ifndef __ITERBINTREE_H__
#define __ITERBINTREE_H__

#define OUT
#define INOUT

typedef struct BinTreeIter_t* BTreeIt;

typedef struct BinTree_t BinTree;

/*------------------------------------------------------------------*/
/*  Type of compare function that must be provided by user.         */
/*------------------------------------------------------------------*/
typedef int (*Less_t)(void*,void*);

/*------------------------------------------------------------------*/
/*  Alloc memory to the struct BinTree and it's data members,       */
/*  if alloc failes 0 will be returned                              */
/*------------------------------------------------------------------*/
BinTree*  BinTreeNew       (Less_t);

/*------------------------------------------------------------------*/
/*  Frees alloc mem of the whole BinTree structure.                 */
/*  Function operates is O(n)                                       */
/*------------------------------------------------------------------*/
void      BinTreeDel       (BinTree*);

/*------------------------------------------------------------------*/
/*  Function returns iterator to the smallest obj in the BinTree    */
/*  determined by Compare Function provided by user.                */
/*  Function operates is O(1)                                       */
/*------------------------------------------------------------------*/
BTreeIt   BinTreeBegin  (BinTree*);

/*------------------------------------------------------------------*/
/*  Function returns iterator to the end of the BinTree. End is     */
/*  next after the largest object and it is out of bounds of the    */
/*  BinTree. Function BinTreePrev on BinTreeEnd will give the last  */
/*  obj in the tree.                                                */
/*  Function operates is O(1)                                       */
/*------------------------------------------------------------------*/
BTreeIt   BinTreeEnd    (BinTree*);

/*------------------------------------------------------------------*/
/*  Function forwards the iterator to the next smallest object in   */
/*  the BinTree.                                                    */
/*  Operation of the function is log(N).                            */
/*------------------------------------------------------------------*/
BTreeIt   BinTreeNext   (BTreeIt);

/*------------------------------------------------------------------*/
/*  Function backwards the iterator to the prev largest object in   */
/*  the BinTree.                                                    */
/*  Operation of the function is log(N).                            */
/*------------------------------------------------------------------*/
BTreeIt   BinTreePrev   (BTreeIt);

/*------------------------------------------------------------------*/
/*  Function returns data of the wanted iterator.                   */
/*  Operation of the function is O(1).                              */
/*------------------------------------------------------------------*/
void*     BinTreeGetData   (BTreeIt);

/*------------------------------------------------------------------*/
/*  Function inserts object to the BinTree, and operates in log(n). */
/*  Function returns Iterator to the inserted data, if insertion    */
/*  isn't succeessful BinTreeEnd() will be returned                 */
/*------------------------------------------------------------------*/
BTreeIt  BinTreeInsert (BinTree*,void* _data);

/*------------------------------------------------------------------*/
/*  Function erases the object of the given iterator,               */
/*  iterator to next object in BinTree is returned                  */
/*------------------------------------------------------------------*/
BTreeIt  BinTreeRemove (BinTree* ,BTreeIt);

/*------------------------------------------------------------------*/
/*  Function returnes num>0 if there are no objects in the BinTree  */
/*  and 0 if there are objects                                      */
/*  Operation of the function is O(1).                              */
/*  Function operates in log(n)                                     */
/*------------------------------------------------------------------*/
int      BinTreeIsEmpty(BinTree*);

/*------------------------------------------------------------------*/
/*  Function returns iterator to first found object in the tree.    */
/*  In case object wasn't found BinTreeEnd() is returned            */
/*  Function operates in log(n)                                     */
/*------------------------------------------------------------------*/
BTreeIt  BinTreeFind (BinTree*,void*);

/*------------------------------------------------------------------*/
/*  Function returnes num>0 if two iterators are equal              */
/*  and 0 if there are not.                                         */
/*  Operation of the function is O(1).                              */
/*------------------------------------------------------------------*/
int      BinTreeIsEqual (BTreeIt _iter1, BTreeIt _iter2);

#endif /* __ITERBINTREE_H__ */
